本题来自力扣167. 两数之和 II - 输入有序数组。难度：中等

暴力破解

先固定一个数然后再循环剩余的数字，挨个相加与目标值比较，时间复杂度O(n²)，没有用上题目条件，非递减顺序排序，不太好

二分查找

先固定一个数，但是第二个数字用二分查找的方法，固定的那个数需要循环时间复杂度为O(n)，二分查找时间复杂度为O(logn)所以总体O(nlogn),写代码时只需要在标准的二分查找上面套一层循环用来遍历那个固定的数就行

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            low, high = i + 1, n - 1		//查找的范围不包括那个固定的数
            while low <= high:
                mid = (low + high) // 2
                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]   #返回的是位置不是索引，所以都加一
                elif numbers[mid] > target - numbers[i]:
                    high = mid - 1
                else:
                    low = mid + 1

双指针

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        length=len(numbers)
        j=length-1
        i=0
        while i<j:
            if numbers[i]+numbers[j]==target:
                return [i+1,j+1]
            elif numbers[i]+numbers[j]>target:
                j-=1
            else:
                i+=1

两个指针一个在尾部一个在头部，值大于目标值的话尾部的那个指针就左移，小于的话头部的那个指针就右移。

至于为什么不会漏项？

比如由一组数[1,2,3,4,5,6,7]

初始i=0,j=6

假设当值(1+7)大于目标值的时候，左移尾部的指针就行，按照之前的还需要7分别于2,3,4,5,6比较，但是显然不需要了。

因为数组从小到大排列，7与最左边的1之和都大于目标值，说明剩余的无需比较，缩小了搜索空间（绿色为遍历第一次比较完成的索引值）

第一次遍历完 j-1

当值(1+6)小于目标值的时候，右移头部的指针，因为(1+6)都小于目标值了，而6在这一层搜索中，为尾部的指针里的为最大值

所以无需比较1与2,3,4,5了（红色为第二次遍历比较完成的索引值）

第二次遍历完i+=1,以此类推，假设第三次值(2+6)大于目标值，（黄色为第二次遍历比较完成的索引值）

经过一次次循环，一定能覆盖所有的索引情况，如果某个循环中两个值加起来符合题意，那么就直接返回，不再继续遍历。

事实上每次比较只需要比较剩余没确认格子中右上角的那个就行，如果小于，那么确定这一列都不符合目标值，如果大于，那么确定这一行都不符合要求。

之所以会成功是因为题目里的条件就是从小到大排列，